#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h>
#include <time.h>

#define MAX_SIZE 100
#define NUM_THREADS 4 // 假设线程数量

typedef struct {
    int tid;
    double (*A)[MAX_SIZE];
    int n;
    sem_t *sem_Division;
    sem_t *sem_Elimination;
} ThreadParam_t;

double A[MAX_SIZE][MAX_SIZE]; // 假设 A 是全局变量
int n; // 假设 n 是全局变量
sem_t sem_Division[NUM_THREADS - 1], sem_Elimination[NUM_THREADS - 1]; // 信号量

void *threadFunc(void *param) {
    ThreadParam_t *p = (ThreadParam_t *)param;
    int tid = p->tid;
    double (*A)[MAX_SIZE] = p->A;
    int n = p->n;
    sem_t *sem_Division = p->sem_Division;
    sem_t *sem_Elimination = p->sem_Elimination;

    // 等待前一个线程完成除法操作
    if (tid > 0)
        sem_wait(&sem_Division[tid - 1]);

    struct timespec start, end;
    clock_gettime(CLOCK_MONOTONIC, &start);

    for (int k = tid; k < n; k += NUM_THREADS) {
        // 除法操作
        for (int j = k + 1; j < n; j++) {
            A[k][j] = A[k][j] / A[k][k];
        }
        A[k][k] = 1.0;

        // 发出信号，通知下一个线程进行除法操作
        if (k < n - 1)
            sem_post(&sem_Division[tid]);

        // 等待所有线程完成除法操作
        if (k == 0)
            for (int i = 0; i < NUM_THREADS - 1; ++i)
                sem_wait(&sem_Division[NUM_THREADS - 2]);

        // 等待前一个线程完成消去操作
        if (tid > 0)
            sem_wait(&sem_Elimination[tid - 1]);

        // 消去操作
        for (int i = k + 1; i < n; i++) {
            for (int j = k + 1; j < n; j++) {
                A[i][j] = A[i][j] - A[i][k] * A[k][j];
            }
            A[i][k] = 0.0;
        }

        // 发出信号，通知下一个线程进行消去操作
        if (k < n - 1)
            sem_post(&sem_Elimination[tid]);
    }

    clock_gettime(CLOCK_MONOTONIC, &end);

    long long seconds = end.tv_sec - start.tv_sec;
    long long ns = end.tv_nsec - start.tv_nsec;
    if (start.tv_nsec > end.tv_nsec) { // 如果开始的时间小于结束的时间
        --seconds;
        ns += 1000000000;
    }
    double elapsed = seconds + ns * 1e-9;
    printf("Thread %d execution time: %f seconds\n", tid, elapsed);

    pthread_exit(NULL);
}

int main() {
    // 初始化信号量
    for (int i = 0; i < NUM_THREADS - 1; ++i) {
        sem_init(&sem_Division[i], 0, 0);
        sem_init(&sem_Elimination[i], 0, 0);
    }

    // 创建线程
    pthread_t handles[NUM_THREADS];
    ThreadParam_t param[NUM_THREADS];
    for (int tid = 0; tid < NUM_THREADS; tid++) {
        param[tid].tid = tid;
        param[tid].A = A;
        param[tid].n = n;
        param[tid].sem_Division = sem_Division;
        param[tid].sem_Elimination = sem_Elimination;
        pthread_create(&handles[tid], NULL, threadFunc, &param[tid]);
    }

    // 等待所有线程结束
    for (int tid = 0; tid < NUM_THREADS; tid++) {
        pthread_join(handles[tid], NULL);
    }

    // 销毁所有信号量
    for (int i = 0; i < NUM_THREADS - 1; ++i) {
        sem_destroy(&sem_Division[i]);
        sem_destroy(&sem_Elimination[i]);
    }

    return 0;
}
